1. Field of the Invention
The present invention relates to a data processor, and more particularly, to an apparatus for determining the relationship between a plurality of data to perform template matching.
2. Description of the Prior Art
In a conventional von-Neumann computer, various instructions are stored in advance as programs in a program memory, and addresses in the program memory are sequentially specified by a program counter so that the instructions are sequentially read out. Thereafter, the instructions are executed.
On the other hand, a data flow type information processor is one of a non von-Neumann type computer having no concept of sequential execution of instructions by a program counter. Such a data flow type information processor employs architecture based on parallel processing of instructions. In the data flow type information processor, immediately after data which are objects of an operation are collected, an instruction can be executed. Further, a plurality of instructions are simultaneously driven by the data, so that programs are executed in parallel in accordance with the natural flow of the data. As a result, it is considered that the time required for the operation is significantly reduced.
FIG. 1 is a block diagram showing one example of a structure of a conventional data flow type information processor to which the present invention is applied. In addition, FIG. 2 is a diagram showing one example of a field structure of a data packet processed by the information processor.
The data packet shown in FIG. 2 comprises a destination field, a data 1 field, and a data 2 field. The destination field stores destination information, the instruction field stores instruction information, and the data 1 field or the data 2 field stores operand data.
The information processor shown in FIG. 1 comprises a program storing portion 1, a paired data detecting portion 2, and an operation processing portion 3. A data flow program shown in FIG. 3 is stored in the program storing portion 1. The program storing portion 1 reads out destination information and instruction information in the data flow program as shown in FIG. 3, by addressing based on the destination information in the inputted data packet, respectively stores the destination information and the instruction information in the destination field and the instruction field in the data packet, and outputs the data packet. The paired data detecting portion 2 queues the data packet outputted from the program storing portion 1. That is, it detects different two data packets having the same destination information, stores operand two data in one of the data packets out of the data packets, for example, the content of the data 1 field shown in FIG. 2 in the data 2 field in the other data packet, and outputs the other data packet. The operation processing portion 3 performs operation processing based on the instruction information with respect to the data packet outputted from the paired data detecting portion 2, stores the result in the data 1 field in the data packet and outputs the data packet to the program storing portion 1.
Meanwhile, the program storing portion 1 and the paired data detecting portion are coupled to each other by two data transmission paths 4. The data transmission paths 4 are coupled to two input ports of the paired data detecting portion 2. The data packet outputted from the program storing portion 1 is selectively inputted to either one of the input ports of the paired data detecting portion 2 depending on whether the operand data is right operand data or left operand data in the operation processing. In addition, the paired data detecting portion 2 and the operation processing portion 3 are coupled to each other by a transmission path 5, and the operation processing portion 3 and the program storing portion 1 are coupled to each other by a transmission path 6.
The data packet circulates through the program storing portion 1, the paired data detecting portion 2, and the operation processing portion 3 in that order, so that operation processing based on the data flow program stored in the program storing portion 1 progresses.
Meanwhile, in the above described paired data detecting portion 2, paired data are detected according to a so-called template matching system. Conventionally, as this template matching system, the following are known: a system of performing processing in a hardware manner using a semiconductor memory device (associative memory) having an associative function, and a system of performing processing in a software manner using a general-purpose memory and a large capacity external memory.
Conventionally, as a semiconductor memory device having an associative function, a semiconductor memory device has been known which is disclosed in, for example, Technical Report of Institute of Electronic and Communication Engineers of Japan (1983) SSD 83-78, pp. 45-52. The semiconductor memory device is a so-called logic-in memory comprising a plurality of memory cells each having a collating and comparing circuit. The logic-in memory as described in the above described document, in which all the memory cells determine collation, is also referred to as a full-associative memory. The full-associative memory comprises a memory cell array having a plurality of memory cells arranged in rows and columns. In the full-associative memory, all the memory cells have a function of determining collation, so that a search along a word direction (row direction) in the memory cell array, and a search along a bit direction (column direction) can be made based on an input of a key word. More specifically, complete determination of collation along the word direction and the bit direction is made.
Thus, in the full-associative memory, complete determination of collation can be made while the area of a unit memory cell is increased. Therefore, the area of the full-associative memory shown in the above described document is increased by approximately six times that of a general-purpose dynamic memory having the same storage capacity.
Additionally, if complete determination of collation is not required, that is, partial determination of collation or determination of collation depending on the condition is made, it becomes redundant to have comparing logic circuits for determination of collation in all the memory cells. Therefore, it is not economic as a semiconductor device.
Thus, if the template matching system is achieved using the associative memory, there is a problem in that it is difficult to configure a large-scale system to a small size, at a low cost.
On the other hand, a case, in which the template matching system is achieved in a software manner without using a special memory, such as the associative memory is superior to a case using the associative memory in terms of memory capacity and economy. On the contrary, the search time of data is greatly fluctuated depending on the value and the content of data. Therefore, another problem occurs in that it is difficult to perform matching processing of all data at a constant processing time, and either the processing speed is reduced or the processing efficiency is decreased.